package ljl.alg.wangzheng_camp.round1.bisection;

/**
 * 怎么感觉我对二分还是不太熟，我日！
 * <p>
 * 我都没认真读题，这个题是搜索二维矩阵 1，也就是每行都比上一行最后一个大，搞错了！
 * 那这两个题解就简单了！
 * <p>
 * 我写了很长，但全是废话！
 * <p>
 * 还是 z 字形查找简单
 * 我实在是累了，以后这种题我一律用最简单的
 * 快的那点效率根本没用
 */
public class _74_search_matrix {
    
    /*
     * 你首先得知道，第一列是升序的，本来就是
     * 找到最后一个，第一个元素不大于 target 的行
     * 然后对这一行二分查找
     * */
    class twice_binary_search {
        public boolean searchMatrix(int[][] matrix, int target) {
            int rowIndex = binarySearchFirstColumn(matrix, target);
            if (rowIndex < 0) {
                return false;
            }
            return binarySearchRow(matrix[rowIndex], target);
        }
        
        public int binarySearchFirstColumn(int[][] matrix, int target) {
            int low = -1, high = matrix.length - 1;
            while (low < high) {
                int mid = (high - low + 1) / 2 + low;
                if (matrix[mid][0] <= target) {
                    low = mid;
                } else {
                    high = mid - 1;
                }
            }
            return low;
        }
        
        public boolean binarySearchRow(int[] row, int target) {
            int low = 0, high = row.length - 1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                if (row[mid] == target) {
                    return true;
                } else if (row[mid] > target) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return false;
        }
    }
}

/*
 * 把矩阵恢复成一个长的升序矩阵，这个也不好想的
 * 但是很简单
 * 1 2 3 4
 * 2 3 4 5
 * */
class once_binary_search {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

/*
 * 我只是想二分查找行或列
 * 我这个复杂度应该是 log(m) * log(n)
 *
 * 简单版的应该是 m * n
 *
 * 我还是套的人家的壳子，不是什么好东西！
 *
 * */
class reluctantly {
    
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j = binarySearch(matrix, i, j, target, true);
            } else {
                i = binarySearch(matrix, i, j, target, false);
            }
            if (i == -1 || j == -1) return false;
        }
        return false;
    }
    
    /*
     * 行：小于等于时停下，返回；也就是大于时还得继续找
     * 列：等于，直接返回；大于，返回上一个
     * */
    int binarySearch(int[][] matrix, int row, int col, int target, boolean byRow) {
        int i = byRow ? 0 : row + 1;
        int j = byRow ? col : matrix.length;
        int res = -1;
        while (i < j) {
            int mid = (i + j) >>> 1;
            int value = byRow ? matrix[row][mid] : matrix[mid][col];
            if (value == target) return mid;
                // value 有点大，对于列式二分可以接受，对于行，不能接受
            else if (value > target) {
                if (!byRow) res = mid;
                j = mid;
            }
            // value 小，列式二分不能接受，行可以
            else {
                if (byRow) res = mid;
                i = mid + 1;
            }
        }
        return res;
    }
}